package com.atguigu.avl;

public class AVLTreeDemo {
    public static void main(String[] args) {
//        int[] arr=new int[]{4,3,6,5,7,8};
        int[] arr=new int[]{10,11,7,6,8,9};
        AVLTree avlTree = new AVLTree();
        for (int i : arr) {
            avlTree.addNode(new Node(i));
        }
        avlTree.infixOrder();
        int leftHeight = avlTree.leftHeight();
        int rightHeight = avlTree.rightHeight();
        System.out.println("left="+leftHeight+",right="+rightHeight);
    }
}

class AVLTree{
    public Node root;

    public void addNode(Node node){
        if(root==null){
            root=node;
        }else{
            root.add(node);
        }
    }

    public void infixOrder(){
        if(root!=null){
            root.infixOrder();
        }else{
            System.out.println("没有任何元素");
        }
    }

    public Node searchNode(int value){
        if(root==null){
            return null;
        }else{
            return root.searchNode(value);
        }
    }

    public Node searchParentNode(int value){
        if(root==null){
            return null;
        }else{
            return root.searchParentNode(value);
        }
    }

    public int leftHeight(){
        if (root==null) {
            return 0;
        }else{
            return root.leftHeight()+1;
        }
    }

    public int rightHeight(){
        if(root==null){
            return 0;
        }else{
            return root.rightHeight()+1;
        }
    }

}


class Node{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + value +
                '}';
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }

    /**
     * 根据值搜索节点地址
     * @param value
     * @return
     */
    public Node searchNode(int value){
        if(this.value==value){
            return this;
        }else if(value<this.value){
            if(this.left==null){
                return null;
            }
            return this.left.searchNode(value);
        }else{
            if(this.right==null){
                return null;
            }
            return this.right.searchNode(value);
        }
    }

    /**
     * 根据值搜索节点的父节点地址
     * @param value
     * @return
     */
    public Node searchParentNode(int value){
        // 执行到这个方法, 已经默认该节点不是目标节点, 即value!=this.value. 且如果有父节点, 只可能是该节点或其子节点
        if(value<this.value){
            if(this.left==null){
                return null;
            }else if(this.left.value==value){
                return this;
            }else{
                return this.left.searchParentNode(value);
            }
        }else{
            if(this.right==null){
                return null;
            }else if(this.right.value==value){
                return this;
            }else{
                return this.right.searchParentNode(value);
            }
        }
    }

    /**
     * 查询当前节点的最大深度. 即当前节点到每一天根节点中的所有长度中, 最长的那一天
     * @return
     */
    public int height(){
        if (left==null&&right==null) {
            return 0;
        }
        if (left==null) {
            return right.height()+1;
        }
        if(right==null){
            return left.height()+1;
        }
        return Math.max(left.height(),right.height())+1;
    }

    /**
     * 当前节点的左子树高度
     * @return
     */
    public int leftHeight(){
        if(left==null){
            return 0;
        }

        return left.height();
    }

    /**
     * 当前节点的右子树高度
     * @return
     */
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.height();
    }

    /**
     * 左旋转(向左旋转)
     * 实际是将当前节点的右子树顶点, 替换为新的顶点
     * 但因为父子关系不变化, 所以仅就值发生变化
     *
     * 旋转的目的是裁枝. 注意, 裁的枝不一定是哪边元素多就裁剪到另一边, 而是哪边长, 就裁到另一边
     * 而旋转达成的效果, 是将左子树的右子树, 或者右子树的左子树, 与原顶点一起裁到另一边.
     *
     * 以右旋转(!)为例,
     * 左子树的左子树上位为左子树, 最大长度-1
     * 右子树部分降级, 最大长度+1.
     * 而原来的左子树的右子树, 仅相当于换了一个同级顶点, 最大长度不变
     *
     * 如果左子树长度过长的原因, 在于左子树的右子树比较突出, 而不是左子树的左子树长度突出, 则直接对顶部的剪裁并不能减少高度差.
     * (因为造成高度差的是`高`原因是原来的左子树的右子树, 也是新的右子树的左子树)
     *
     * 此时, 应该先对左子树进行左旋转, 旋转可能导致两种情况:
     * 1. 最大高度, 系原左-右-左子树导致的, 则该次旋转, 虽不能导致最大高度减少, 但会将左-右-左子树挪到左-左-右部分, 下一次顶部的右旋转后必定会导致最大高度-1
     * 2. 最大高度, 系原左-右-右子树导致的, 则该次旋转, 会使该子树变为左-右子树, 进而使其最大高度-1, 进而导致顶部的最大高度-1
     *
     */
    public void leftRotate(){
        // 注:由于本流程从头到尾并没有修改过当前节点的父级节点!!!(实际是通过变更值实现的)

        // 1. 创建一个新的节点, 并赋值当前节点的值
        Node temp = new Node(value);

        // 2. 将当前节点的左子树, 赋给新节点的左子树
        temp.left=left;

        // 3. 将当前节点的右子树的左子树, 赋给新节点的右子树
        temp.right=right.left;

        // 4. 当前节点的值, 等于右子节点的值(相当于从值上变换了顶点)
        value=right.value;

        // 5. 当前节点的左子树, 是新节点
        left=temp;

        // 5. 当前节点的右子树, 是右子树的右子树
        right=right.right;

        // 做完上面一同操作, 相当于把原来的右子树节点扔掉了

    }

    public void rightRotate(){
        Node temp=new Node(value);
        temp.left=left.right;
        temp.right=right;
        value=left.value;
        left=left.left;
        right=temp;
    }

    /**
     * 增加节点
     * 按照中序二叉树的方式增加
     * @param node
     */
    public void add(Node node){
        if(this.value>node.value){
            if(this.left==null){
                this.left=node;
            }else{
                this.left.add(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);
            }
        }

        // 增加完节点后, 进行检查旋转
        int leftHeight = leftHeight();
        int rightHeight = rightHeight();
        if(leftHeight - rightHeight >1){
            // 由于leftHeight>1, 所以left!=null必为true
            if(left.rightHeight()-left.leftHeight()>0){
                left.leftRotate();
            }
            rightRotate();
        }
        if(rightHeight - leftHeight >1){
            // 由于rightHeight>1, 所以right!=null必为true
            if(right.leftHeight()-right.leftHeight()>0){
                right.rightRotate();
            }
            leftRotate();
        }

    }

}

